In digital communications, the viterbi decoding algorithm is used to decode convolutional coded bits. Convolutional coded bits are generated by passing the message bit sequence through a linear finite-state shift register one symbol at a time. The convolutional encoder is characterized by the length of the shift register, number of input and output bits, and the connections between the shift registers. The viterbi decoding algorithm calculates the log likelihood function for each path at each level of the trellis diagram for the received sequence, and selects the path having the largest log likelihood among those merging at each node of that level, while discarding the other paths. The selected path is called a surviving path. Thereupon, the most likely received message bit sequence is deduced.
A common practice at the transmitter side is to append a sequence of zero bits to the message bits to force the convolutional encoder memory into state zero. Such sequence of bits is known as tail bits, and they are of the same length as the encoder memory. The viterbi decoder uses the tail bits as a priori information to construct a conclusive trellis, namely, the trellis can be “terminated”, which means that the number of surviving paths at the end of the trellis can be progressively reduced to only two possibilities.
The method of decoding tail bits is similar to that of decoding message bits. At each node of the tail bits in the trellis, the metrics for all branches are calculated. However, the number of surviving paths at tail bit nodes is no longer equal to the constraint length (i.e., the number of stages in the convolutional encoder), because the number of branches is reduced exponentially at each node. The number of surviving paths at tail bit nodes is half of the number of branches at that node. This is because for binary decoding algorithms, there are two paths at each node of the trellis diagram, and only one branch survives at each node during decoding.
Error detection is needed to detect errors in decoding. It is usually done by appending additional bits, such as CRC bits, to the message bits at the encoder side, and correspondingly adding additional functions, such as a CRC checker, after the decoder. However, transmitting CRC bits is sometimes not a favourable option. In order to avoid transmitting such additional CRC bits, it is preferable to perform an error detection process using only convolutional coded message and tail bits. This requires the viterbi algorithm to be slightly modified.
An example of such a requirement is the 3GPP HSDPA HS-SCCH part I decoding. The decoder at this stage is required to make a decision of whether the decoded bits are reliable or not, without the help of CRC bits. A Viterbi decoding algorithm can calculate the reliability of the decoded bits at any node, including those at the tail bit positions (i.e. the tail bits). Tail bits are known to be all zeros, therefore, if the decoded tail bits are not all zeros, this means that decoding error has occurred in the tail bits and maybe in the message bits.
The Yamamoto-Itoh algorithm is a modified decoding method which allows the viterbi algorithm to calculate the reliability of the decoded message bits. At every level of the trellis, the Yamamoto-Itoh algorithm labels each node in the level as either successful or failure. This is done by calculating the difference between the metrics of the two paths that merge into a node. If the difference is larger than a specified constant, the node is labeled as successful; if not, it is labeled as failure. The decoding is considered to be erroneous if all nodes are labeled as failure at any level.
This algorithm requires computation in addition to the viterbi algorithm at every level (i.e. at the decoding of every message symbol). Therefore, the complexity of this algorithm increases linearly with the number of message bits.